/*
 * @lc app=leetcode.cn id=1091 lang=typescript
 *
 * [1091] 二进制矩阵中的最短路径
 */

// @lc code=start
// 搜索状态
class Data {
  i: number;
  j: number;
  length: number;
  constructor(i: number = 0, j: number = 0, length: number = 1) {
    this.i = i;
    this.j = j;
    this.length = length;
  }
}

function shortestPathBinaryMatrix(grid: number[][]): number {
  if (grid[0][0] !== 0) return -1;
  // 8个方向
  const dir = [
    [-1, 0],
    [-1, 1],
    [0, 1],
    [1, 1],
    [1, 0],
    [1, -1],
    [0, -1],
    [-1, -1],
  ];
  let ans = -1;
  const n = grid.length;
  const visited = new Array(n).fill(0).map(() => new Array(n).fill(0));
  const queue: Data[] = [];
  // 初始化队列和已访问数组
  visited[0][0] = 1;
  queue.push(new Data(0, 0, 1));
  while (queue.length) {
    const data = queue.shift();
    // 到达目标
    if (data.i === n - 1 && data.j === n - 1) {
      ans = data.length;
      break;
    }
    // 向8个方向扩展
    for (let i = 0; i < dir.length; i++) {
      let x = dir[i][0] + data.i;
      let y = dir[i][1] + data.j;
      if (x < 0 || x >= n) continue;
      if (y < 0 || y >= n) continue;
      if (visited[x][y] === 1) continue;
      if (grid[x][y] === 1) continue;
      visited[x][y] = 1;
      queue.push(new Data(x, y, data.length + 1));
    }
  }

  return ans;
}
// @lc code=end
